import java.util.*;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
    public void DLR(TreeNode t){
        if(t==null){
            return;
        }
        while(t.left!=null){
            System.out.print(t.val+" ");
        }
        while()
    }

aa






    public int getHigh(TreeNode t){
        if(t==null){
            return 0;
        }
        int leftTree=getHigh(t.left);
        int rightTree=getHigh(t.right);
        return Math.max(leftTree,rightTree)+1;
    }







    static int size=0;
    public int getKsize(int k,TreeNode t){
        if(t==null){
            return 0;
        }
        if(k==1){
            size++;
        }
        getKsize(k--,t.left);
        getKsize(k--, t.right);
        return size;
    }
}
class Solution{
    static int size=0;
    public int getKsize(int k,TreeNode t){
        if(t==null){
            return 0;
        }
        if(k==1){
            size++;
        }
        getKsize(k--,t.left);
        getKsize(k--, t.right);
        return size;
    }
}






class Solution12{//二叉树节点个数
    static int size=0;
    public int getSize(TreeNode t){
        if(t==null){
            return 0;
        }
        size++;
        getSize(t.left);
        getSize(t.right);
        return size;
    }
}





class Solution11 {//判断是否为平衡二叉树
    public int MAXtree(TreeNode t){
        if(t==null){
            return 0;
        }
        int a=MAXtree(t.left);
        int b=MAXtree(t.right);
        if(a>=0&&b>=0&&Math.abs(a-b)<2){
            return Math.max(a,b)+1;
        }else{

        }return -1;
    }
    public boolean isBalanced(TreeNode root) {
        return MAXtree(root)<0?false:true;
    }
}







class Solution10 {//对称二叉树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }else if(p==null||q==null){
            return false;
        }else{
            return p.val==q.val&&isSameTree(p.left,q.right)&&isSameTree(p.right,q.left);
        }
    }
    public boolean isSymmetric(TreeNode root) {
        return isSameTree(root.left,root.right);
    }
}








class Solution9 {//二叉树的最大深度
    public int maxDepth(TreeNode root) {
        if(root==null){
            return 0;
        }
        int Left=maxDepth(root.left);
        int Right=maxDepth(root.right);
        return Left>Right?Left+1:Right+1;
    }
}








class Solution8 {//另一棵树的子树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }else if(p==null||q==null){
            return false;
        }else if(p.val!=q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
    }
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root==null||subRoot==null){
            return false;
        }
        if(isSameTree(root,subRoot)){
            return true;
        }
        if(isSubtree(root.left,subRoot)){
            return true;
        }
        if(isSubtree(root.right,subRoot)){
            return true;
        }
        return false;
    }
}







class Solution7 {//相同的树
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p==null&&q==null){
            return true;
        }else if(p==null||q==null){
            return false;
        }else if(p.val!=q.val){
            return false;
        }else{
            return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
        }
    }
}

















class Solution6 {//二叉树后序遍历
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null){
            return list;
        }
        List<Integer> treeleft=postorderTraversal(root.left);
        list.addAll(treeleft);
        List<Integer> treeright=postorderTraversal(root.right);
        list.addAll(treeright);
        list.add(root.val);
        return list;
    }
}









class Solution5 {//二叉树后序遍历
    List<Integer> list=new LinkedList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        postorderTraversal(root.left);
        postorderTraversal(root.right);
        list.add(root.val);
        return list;
    }
}








class Solution4 {//二叉树中序遍历
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null){
            return list;
        }
        List<Integer> treeLeft=inorderTraversal(root.left);
        list.addAll(treeLeft);
        list.add(root.val);
        List<Integer> treeRight=inorderTraversal(root.right);
        list.addAll(treeRight);
        return list;
    }
}







class Solution3 {//二叉树中序遍历
    List<Integer> list=new LinkedList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }
}




class Solution2 {//二叉树前序遍历
    List<Integer> list=new LinkedList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        if(root==null){
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
}





class Solution1 {//二叉树前序遍历
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list=new LinkedList<>();
        if(root==null){
            return list;
        }
        list.add(root.val);
        List<Integer> treeleft=preorderTraversal(root.left);
        list.addAll(treeleft);
        List<Integer> treeright=preorderTraversal(root.right);
        list.addAll(treeright);
        return list;
    }
}